package com.algorithm.introduction.lectureone;

import com.algorithm.util.GenerateBigData;

public class PeakFinding {

	private static void peakFindNormal(int[] bigArray, int arrayLength) {
		if (bigArray[0] >= bigArray[1]) {
			System.out.println(0 + ":" + bigArray[0]);
			return;
		}
		for (int i=1; i < arrayLength - 1; i++) {
			if (bigArray[i] >= bigArray[i-1] && bigArray[i] >= bigArray[i+1]) {
				System.out.println(i+ ":" +bigArray[i]);
				return;
			}
		}
		if (bigArray[arrayLength-1] >= bigArray[arrayLength-2]) {
			System.out.println((arrayLength-1)+ ":" + bigArray[arrayLength-1]);
		}
		
	}
	

	private static void peakFindBinary(int[] bigArray, int low, int high) {
		int middle = (low + high) / 2;
		if (middle != low) {
			if (bigArray[middle] < bigArray[middle+1]) {
				peakFindBinary(bigArray, middle+1, high);
			} else if (bigArray[middle] < bigArray[middle-1]) {
				peakFindBinary(bigArray, low, middle-1);
			} else {
				System.out.println(middle + ":" + bigArray[middle]);
			}
		} else {
			if (bigArray[middle] < bigArray[middle+1]) {
				System.out.println(middle + ":" + bigArray[middle+1]);
			} else {
				System.out.println(middle + ":" + bigArray[middle]);
			}
		}
		
	}
	
	private static void peakFindBinaryCircle(int[] bigArray, int low, int high) {
		while (high - low != 1) {
			int middle = (low + high) / 2;
			if (bigArray[middle] < bigArray[middle+1]) {
				low = middle+1;
			} else if (bigArray[middle] < bigArray[middle-1]) {
				high = middle - 1;
			} else {
				System.out.println(middle + ":" + bigArray[middle]);
				break;
			}
		}
		if (high - low == 1) {
			if (bigArray[low] < bigArray[high]) {
				System.out.println(high + ":" + bigArray[high]);
			} else {
				System.out.println(low + ":" + bigArray[low]);
			}
		}
	}


	private static void nearColFindPeak(int[][] matrix, int x, int y, int lowRow, int highRow) {
		if (matrix[x][y] > matrix[x][y+1]) {
			System.out.println(x+ "-" + y + ":" + matrix[x][y]);
		} else {
			int maxMark2 = lowRow;
			for (int i = lowRow; i <= highRow; i++) {
				if (matrix[i][y+1] > matrix[maxMark2][y+1]) {
					maxMark2 = i;
				}
			}
			System.out.println(maxMark2+ "-" + (y+1) + ":" + matrix[maxMark2][y+1]);
		}
	}

	private static void peakFindBinary2D(int[][] bigMatrix, int lowRow, int highRow, int lowCol, int highCol) {
		int middleCol = (lowCol + highCol) / 2;
		if (middleCol != lowCol) {
			int maxMark = lowRow;
			for (int i = lowRow; i <= highRow; i++) {
				if (bigMatrix[i][middleCol] > bigMatrix[maxMark][middleCol]) {
					maxMark = i;
				}
			}
			if (bigMatrix[maxMark][middleCol] < bigMatrix[maxMark][middleCol-1]) {
				peakFindBinary2D(bigMatrix, lowRow, highRow, lowCol, middleCol);
			} else if (bigMatrix[maxMark][middleCol] < bigMatrix[maxMark][middleCol+1]) {
				peakFindBinary2D(bigMatrix, lowRow, highRow, middleCol, highCol);
			} else {
				System.out.println(maxMark+ "-" + middleCol + ":" + bigMatrix[maxMark][middleCol]);
			}
		} else {
			int maxMark = lowRow;
			for (int i = lowRow; i <= highRow; i++) {
				if (bigMatrix[i][middleCol] > bigMatrix[maxMark][middleCol]) {
					maxMark = i;
				}
			}
			nearColFindPeak(bigMatrix, maxMark, middleCol, lowRow, highRow);
		}

	}


	private static boolean isBest(int[][] matrix, int i, int j, int x, int y) {
		return x == -1 || y == -1 || matrix[x][y] < matrix[i][j];
	}



	private static void peakFindBinary2DBest(int[][] bigMatrix, int lowRow, int highRow, int lowCol, int highCol, boolean rowsplit, int bestSeenRow, int bestSeenCol) {
		if (rowsplit) {
			int middleRow = lowRow + highRow / 2;
			if (middleRow != lowRow) {
				int maxMark = lowCol;
				for (int i = lowCol; i <= highCol; i++) {
					if (bigMatrix[middleRow][i] > bigMatrix[middleRow][maxMark]) {
						maxMark = i;
					}
				}
				if (bigMatrix[middleRow][maxMark] < bigMatrix[middleRow-1][maxMark] && isBest(bigMatrix,middleRow-1, maxMark, bestSeenRow, bestSeenCol)) {
					bestSeenRow = middleRow-1;
					bestSeenCol = maxMark;
					peakFindBinary2DBest(bigMatrix, lowRow, middleRow, lowCol, highCol, !rowsplit, bestSeenRow, bestSeenCol);
				} else if (bigMatrix[middleRow][maxMark] < bigMatrix[middleRow+1][maxMark] && isBest(bigMatrix, middleRow+1, maxMark, bestSeenRow, bestSeenCol)) {
					bestSeenRow = middleRow+1;
					bestSeenCol = maxMark;
					peakFindBinary2DBest(bigMatrix, middleRow, highRow, lowCol, highCol, !rowsplit, bestSeenRow, bestSeenCol);
				} else if (isBest(bigMatrix, middleRow, maxMark, bestSeenRow, bestSeenCol)) {
					System.out.println(middleRow+ "-" + maxMark + ":" + bigMatrix[middleRow][maxMark]);
				} else {
					if (bestSeenRow > middleRow) {
						peakFindBinary2DBest(bigMatrix, middleRow, highRow, lowCol, highCol, !rowsplit, bestSeenRow, bestSeenCol);
					} else {
						peakFindBinary2DBest(bigMatrix, lowRow, middleRow, lowCol, highCol, !rowsplit, bestSeenRow, bestSeenCol);
					}
				}
			} else {
				int maxMark = lowCol;
				for (int i = lowCol; i <= highCol; i++) {
					if (bigMatrix[middleRow][i] > bigMatrix[middleRow][maxMark]) {
						maxMark = i;
					}
				}
				if (bigMatrix[middleRow][maxMark] > bigMatrix[middleRow+1][maxMark]) {
					System.out.println(middleRow+ "-" + maxMark + ":" + bigMatrix[middleRow][maxMark]);
				} else {
					int maxMark2 = lowCol;
					for (int i = lowCol; i <= highCol; i++) {
						if (bigMatrix[middleRow][i] > bigMatrix[middleRow][maxMark2]) {
							maxMark2 = i;
						}
					}
					System.out.println(highRow+ "-" + maxMark2 + ":" + bigMatrix[highRow][maxMark2]);
				}
			}
		} else {
			int middleCol = lowCol + highCol / 2;
			if (middleCol != lowCol) {
				int maxMark = lowRow;
				for (int i = lowRow; i <= highRow; i++) {
					if (bigMatrix[i][middleCol] > bigMatrix[maxMark][middleCol]) {
						maxMark = i;
					}
				}
				if (bigMatrix[maxMark][middleCol] < bigMatrix[maxMark][middleCol-1] && isBest(bigMatrix, maxMark, middleCol-1, bestSeenRow, bestSeenCol)) {
					bestSeenRow = maxMark;
					bestSeenCol = middleCol-1;
					peakFindBinary2DBest(bigMatrix, lowRow, highRow, lowCol, middleCol, !rowsplit, bestSeenRow, bestSeenCol);
				} else if (bigMatrix[maxMark][middleCol] < bigMatrix[maxMark][middleCol+1] && isBest(bigMatrix, maxMark, middleCol+1, bestSeenRow, bestSeenCol)) {
					bestSeenRow = maxMark;
					bestSeenCol = middleCol+1;
					peakFindBinary2DBest(bigMatrix, lowRow, highRow, middleCol, highCol, !rowsplit, bestSeenRow, bestSeenCol);
				} else if (isBest(bigMatrix, maxMark, middleCol, bestSeenRow, bestSeenCol)) {
					System.out.println(maxMark+ "-" + middleCol + ":" + bigMatrix[maxMark][middleCol]);
				} else {
					if (bestSeenCol > middleCol) {
						peakFindBinary2DBest(bigMatrix, lowRow, highRow, middleCol, highCol, !rowsplit, bestSeenRow, bestSeenCol);
					} else {
						peakFindBinary2DBest(bigMatrix, lowRow, highRow, lowCol, middleCol, !rowsplit, bestSeenRow, bestSeenCol);
					}
				}
			} else {
				int maxMark = lowRow;
				for (int i = lowRow; i <= highRow; i++) {
					if (bigMatrix[i][middleCol] > bigMatrix[maxMark][middleCol]) {
						maxMark = i;
					}
				}
				nearColFindPeak(bigMatrix, maxMark, middleCol, lowRow, highRow);
			}
		}

	}

	public static void main(String[] args) {
		int[] bigArray;
		//bigArray = GenerateBigData.generateBigArray();
		//int[][] bigMatrix = GenerateBigData.generateBigMatrix();
		int[][] matrix = GenerateBigData.generateMatrix();
		long start;
		long end;
		//注意：递归和循环的时间在一个数量级，有些不准确。
		start = System.nanoTime();
		//peakFindBinaryCircle(bigArray, 0, 100000000 - 1);
		//peakFindBinary(bigArray, 0, 100000000 - 1);
		end = System.nanoTime();
		System.out.println("时间:" + (end - start));
		start = System.nanoTime();
		//peakFindNormal(bigArray, 100000000);
		end = System.nanoTime();
		System.out.println("时间:" + (end - start));

		//peakFindBinary2D(bigMatrix, 0, 10000-1, 0, 10000-1);
		peakFindBinary2DBest(matrix, 0, 7, 0, 6, true, -1, -1);

	}
	
}
